package com.thesis.algorithm;

import java.io.BufferedWriter;
import java.io.DataInputStream;
import java.io.DataOutputStream;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.io.Writer;
import java.util.LinkedList;

import com.thesis.algorithm.Sequence;
import com.thesis.algorithm.SequenceElement;
import com.thesis.utils.BusControl;
import com.thesis.utils.BusRoute;
import com.thesis.utils.CONSTANTS;
import com.thesis.utils.Utils;

public class SequenceMatching {

	public LinkedList<Sequence> seqs = new LinkedList<Sequence>();
	public LinkedList<Sequence> refined_seqs = new LinkedList<Sequence>();
	BusControl busController = new BusControl();
	final public static int MODE_READ_FROM_TRAINFOLDER = 0;
	final public static int MODE_READ_FROM_BINARYFILE = 1;
	public int singleInterestedRoute;
	public boolean containsOnlyOneRoute = false;

	/**
	 * 
	 */
	public SequenceMatching(int MODE) {
		if (MODE == MODE_READ_FROM_TRAINFOLDER) {

			// REPRODUCE FILES
			FileConverter fc = new FileConverter(CONSTANTS.TRAIN_DATA_FOLDER);
			LinkedList<Sequence> seqs = busController
					.produceTrainSequence(fc.listOfDevices);
			for (int i = 0; i < seqs.size(); i++) {
				refined_seqs.add(seqs.get(i).refineSequence());
			}
			// this.writeSequenceToBinary(seqs);
			this.writeSequenceToBinary(refined_seqs);
		} else if (MODE == MODE_READ_FROM_BINARYFILE) {
			try {
				DataInputStream in = new DataInputStream(new FileInputStream(
						CONSTANTS.REFINED_SEQUENCE_BINARY_FILEPATH));
				refined_seqs = readSequenceFromBinary(in);
				in.close();
			} catch (Exception e) {
				e.printStackTrace();
			}
		}

	}

	
	
	//=============================================
	//=== FOR VELOCITY ESTIMATION
	//=============================================
	
	
	
	
	
	
	
	
	
	
	
	//=============================================
	//=== THE REST
	//=============================================
	
	public LinkedList<Character> matchBusStop(Sequence sequence, Writer out,
			int[] interestedBusRoute) throws IOException {
		sequence = sequence.refineSequence();
		out.write("\n======\nmatch bus stop\n");

		Sequence[] matchedSeqs = new Sequence[interestedBusRoute.length];
		
		int[] score = new int[interestedBusRoute.length];

		int index = 0;
		for (int i = 0; i < interestedBusRoute.length; i++) {
			index = findBusrouteIndex(interestedBusRoute[i]);
			if (index != -1) {
				if (refined_seqs.get(index).BusRouteID == sequence.BusRouteID)
					System.out.println("HERE");
				matchedSeqs[i] = lcs(refined_seqs.get(index), sequence, out);

				score[i] = matchedSeqs[i].score();
				if (score[i] > 0)
					out.write("Score: " + score[i] + " "
							+ matchedSeqs[i].toString() + "\n");
			} else
				score[i] = 0;
		}
		// TODO: We can vary minscore (minscore=*.8minscore to maxout accuracy)
		double minScore = Utils.max(score);
		// minScore = minScore*0.8;

		// TODO: debug tools
		int[] matchedBusroute = Utils.findAllMaxInArray(score);
		// out.write("Score array: ");
		// out.write(Utils.arrayToString(score) + "\n");
		// out.write("Interested sequence  list: ");
		// out.write(Utils.arrayToString(matchedBusroute) + "\n");
		// out.write("Match busroute  list:\n");
		for (int i = 0; i < matchedBusroute.length; i++) {
			if (matchedSeqs[matchedBusroute[i]] != null) {
				out.write(matchedSeqs[matchedBusroute[i]].toString() + "\n");
				//Sequence s = attempToMatch(sequence,	matchedSeqs[matchedBusroute[i]]);
				//out.write("ATTEMP " + s.score() + " SEQUENCE: " + s.toString()+ "\n");
			} else
				out.write("NULL === CHECK HERE");
		}
		out.flush();

		return allLastBustop(matchedSeqs, minScore,	sequence.getLast().Observation, out);
	}

	private Sequence attempToMatch(Sequence testsequence,
			Sequence matchedsequence) {
		Sequence result = new Sequence();
		Sequence refinematchedsequence = new Sequence();
		Sequence refinetestsequence = new Sequence();
		for (SequenceElement se : matchedsequence.sequenceinFile) {
			if (refinematchedsequence.size() == 0) {
				refinematchedsequence.add(new SequenceElement(se.Observation,
						se.State, se.Lac, se.Repetition));
			} else {
				if (se.Observation == refinematchedsequence.sequenceinFile
						.getLast().Observation) {
					refinematchedsequence.sequenceinFile.getLast().Repetition += se.Repetition;
				} else {
					refinematchedsequence.add(new SequenceElement(
							se.Observation, se.State, se.Lac, se.Repetition));
				}
			}
		}
		for (SequenceElement se : testsequence.sequenceinFile) {
			if (refinetestsequence.size() == 0) {
				refinetestsequence.add(new SequenceElement(se.Observation,
						se.State, se.Lac, se.Repetition));
			} else {
				if (se.Observation == refinetestsequence.sequenceinFile
						.getLast().Observation) {
					refinetestsequence.sequenceinFile.getLast().Repetition += se.Repetition;
				} else {
					refinetestsequence.add(new SequenceElement(se.Observation,
							se.State, se.Lac, se.Repetition));
				}
			}
		}
		int i = 0;
		int j = 0;
		boolean dontaddj = false;
		int countmatched = 0;
		int counttest = 0;
		SequenceElement setest = null;
		SequenceElement sematched = null;
		while (true) {
			setest = refinetestsequence.get(i);
			sematched = refinematchedsequence.get(j);
			if (dontaddj == false)
				countmatched += sematched.Repetition;
			else
				dontaddj = false;
			counttest += setest.Repetition;

			if (setest.Observation == sematched.Observation) {
				if (countmatched == counttest) {
					i++;
					j++;
					countmatched = 0;
					counttest = 0;
				} else if (countmatched < counttest) {
					sematched.Repetition += (counttest - countmatched);
					i++;
					j++;
					countmatched = 0;
					counttest = 0;
				} else {
					i++;
					dontaddj = true;
				}
			} else {
				i++;
				dontaddj = true;
			}
			if (i == refinetestsequence.size()
					&& j == refinematchedsequence.size())
				break;
			if (i == refinetestsequence.size()
					|| j == refinematchedsequence.size()) {
				if (refinetestsequence.score() > refinematchedsequence.score())
					refinematchedsequence.sequenceinFile.getLast().Repetition += (refinetestsequence
							.score() - refinematchedsequence.score());
				break;
			}

		}
		for (SequenceElement se : matchedsequence.sequenceinFile) {
			result.add(new SequenceElement(se));
		}
		i = 0;
		j = 0;
		countmatched = 0;
		int countresult = 0;
		SequenceElement seresult = null;
		sematched = null;
		boolean dontaddi = false;
		while (true) {
			seresult = result.get(j);
			sematched = refinematchedsequence.get(i);
			if (dontaddi == false)
				countmatched += sematched.Repetition;
			else
				dontaddi = false;
			countresult += seresult.Repetition;

			if (seresult.Observation == sematched.Observation) {
				if (countmatched == countresult) {
					i++;
					j++;
					countmatched = 0;
					countresult = 0;
				} else if (countresult < countmatched) {
					j++;
					dontaddi = true;
				} else {
					System.err.println("Something wrong:  sequence matching");
				}
			} else {
				i++;
				result.get(j - 1).Repetition += (countmatched - (countresult - result
						.get(j).Repetition));
				countmatched = 0;
				countresult = 0;
			}
			if (i == refinematchedsequence.size() && j == result.size())
				break;
			if (i == refinematchedsequence.size() || j == result.size()) {
				if (refinematchedsequence.score() > result.score())
					result.sequenceinFile.getLast().Repetition += (refinematchedsequence
							.score() - result.score());

				break;
			}

		}
		if (result.score() != testsequence.score()) {
			System.err.println("SUM TING RON");
		}
		result.BusRouteID = matchedsequence.BusRouteID;
		return result;
	}

	public Sequence matchAndReturnSequence(Sequence sequence, Writer out,
			int[] interestedBusRoute) throws IOException {
		Sequence result = new Sequence();
		sequence = sequence.refineSequence();
		Sequence[] matchedSeqs = new Sequence[interestedBusRoute.length];
		int[] score = new int[interestedBusRoute.length];
		int index = 0;

		for (int i = 0; i < interestedBusRoute.length; i++) {
			index = findBusrouteIndex(interestedBusRoute[i]);
			if (index != -1) {
				if (refined_seqs.get(index).BusRouteID == sequence.BusRouteID)
					matchedSeqs[i] = lcs(refined_seqs.get(index), sequence, out);
				if (matchedSeqs[i] != null)
					score[i] = matchedSeqs[i].score();

			} else
				score[i] = 0;
		}

		int matchedIndex = Utils.positionOfMax(score);
//		out.write("Score before:" + matchedSeqs[matchedIndex].score() + " "
//				+ matchedSeqs[matchedIndex].toString() + "\n");
//		refineLength(sequence, matchedSeqs[matchedIndex]);
		result = attempToMatch(sequence, matchedSeqs[matchedIndex]);
		return result;
	}

	private void refineLength(Sequence sequence, Sequence matchedSeq) {
		if (sequence.score() == matchedSeq.score())
			return;

		char currentObservation = sequence.get(0).Observation;
		int currentScore = sequence.get(0).Repetition;

		for (int i = 1; i < sequence.size(); i++) {
			if (sequence.get(i).Observation == currentObservation)
				currentScore += sequence.get(i).Repetition;
			else {
				// found the observation change
				// do something
				insertScore(matchedSeq, currentObservation, currentScore);

				// update observation and score
				currentObservation = sequence.get(i).Observation;
				currentScore = sequence.get(i).Repetition;
			}
		}
	}

	private void insertScore(Sequence sequence, char observation, int score) {
		int i = 0;
		for (; i < sequence.size(); i++) {
			if (sequence.get(i).Observation == observation)
				break;
		}

		int accumulatedScore = 0;
		for (; i < sequence.size(); ++i)
			if (sequence.get(i).Observation != observation)
				break;
			else
				accumulatedScore += sequence.get(i).Repetition;

		if (i == sequence.size()
				&& observation != sequence.get(i - 1).Observation)
			// not found the place
			return;

		if (accumulatedScore < score)
			sequence.get(i - 1).Repetition += score - accumulatedScore;
	}

	public LinkedList<Character> allLastBustop(Sequence[] seqs,
			double minScore, char observation, Writer out) throws IOException {

		Sequence temp = null;
		LinkedList<Character> result = new LinkedList<Character>();
		for (Sequence seq : seqs) {
			if (seq != null && seq.score() >= minScore && seq.size() != 0) {
				out.write("1111111111\n");
				result.add(seq.getLast().State);
				singleInterestedRoute = seq.BusRouteID;
				temp = seq;
			}
		}

		// refine interested Route
		Utils.removeDuplicate(result);
		out.write("\n==" + Utils.linkedListToString(result) + "\n");
		if (result.size() == 1)
			containsOnlyOneRoute = true;
		else
			containsOnlyOneRoute = false;

		if (result.size() == 1) {
			 BusRoute br = busController.getBusRoute((short) temp.BusRouteID);
			 result.add(br.getNext(result.get(0)));
			 if (temp.size() - 2 >= 0)
			 result.add(temp.get(temp.size() - 2).State);
		}
		return result;
	}

	private int findBusrouteIndex(int busrouteID) {
		for (int i = 0; i < refined_seqs.size(); i++) {
			if (refined_seqs.get(i).BusRouteID == busrouteID)
				return i;
		}
		return -1;
	}

	public static String lcs(String a, String b) {
		int[][] lengths = new int[a.length() + 1][b.length() + 1];

		// row 0 and column 0 are initialized to 0 already
		for (int i = 0; i < a.length(); i++)
			for (int j = 0; j < b.length(); j++)
				if (a.charAt(i) == b.charAt(j))
					lengths[i + 1][j + 1] = lengths[i][j] + 1;
				else
					lengths[i + 1][j + 1] = Math.max(lengths[i + 1][j],
							lengths[i][j + 1]);

		// read the substring out from the matrix
		StringBuffer sb = new StringBuffer();
		for (int x = a.length(), y = b.length(); x != 0 && y != 0;) {
			if (lengths[x][y] == lengths[x - 1][y])
				x--;
			else if (lengths[x][y] == lengths[x][y - 1])
				y--;
			else {
				assert a.charAt(x - 1) == b.charAt(y - 1);
				sb.append(a.charAt(x - 1));
				x--;
				y--;
			}
		}
		return sb.reverse().toString();
	}

	public static Sequence lcs(Sequence a, Sequence b, Writer out) {

		char[][] lengths = new char[a.size() + 1][b.size() + 1];

		// row 0 and column 0 are initialized to 0 already
		for (int i = 0; i < a.size(); i++)
			for (int j = 0; j < b.size(); j++)
				if (a.get(i).Observation == b.get(j).Observation)
					lengths[i + 1][j + 1] = (char) (lengths[i][j] + 1);
				else
					lengths[i + 1][j + 1] = (char) Math.max(lengths[i + 1][j],
							lengths[i][j + 1]);

		// read the substring out from the matrix
		Sequence result = new Sequence();
		for (int x = a.size(), y = b.size(); x != 0 && y != 0;) {
			if (lengths[x][y] == lengths[x - 1][y])
				x--;
			else if (lengths[x][y] == lengths[x][y - 1])
				y--;
			else {
				int scoreA = a.get(x - 1).Repetition;
				int scoreB = b.get(y - 1).Repetition; // testdata, must be int,
														// because char is
														// unsigned

				int index = 0;
				int xx = x - 1;
				while ((scoreB > 0) && (xx < a.size())) {
					if (a.get(xx).Observation != b.get(y - 1).Observation) {
						// TODO: check more about score here
						// result.sequenceinFile.getLast().Repetition+=scoreB;
						break;
					}
					SequenceElement se = new SequenceElement(a.get(xx));
					scoreB -= se.Repetition;

					if (scoreB < 0)
						se.Repetition += scoreB;
					result.sequenceinFile.add(index, se);

					xx += 1;
					++index;
				}
				x--;
				y--;

			}
		}
		// TODO: check if needed
		if (a.BusRouteID != 0)
			result.BusRouteID = a.BusRouteID;
		else if (b.BusRouteID != 0)
			result.BusRouteID = b.BusRouteID;
		return result;
	}

	public static Sequence lcs(Sequence a, Sequence b) {

		char[][] lengths = new char[a.size() + 1][b.size() + 1];

		// row 0 and column 0 are initialized to 0 already
		for (int i = 0; i < a.size(); i++)
			for (int j = 0; j < b.size(); j++)
				if (a.get(i).Observation == b.get(j).Observation)
					lengths[i + 1][j + 1] = (char) (lengths[i][j] + 1);
				else
					lengths[i + 1][j + 1] = (char) Math.max(lengths[i + 1][j],
							lengths[i][j + 1]);

		// read the substring out from the matrix
		Sequence result = new Sequence();
		for (int x = a.size(), y = b.size(); x != 0 && y != 0;) {
			if (lengths[x][y] == lengths[x - 1][y])
				x--;
			else if (lengths[x][y] == lengths[x][y - 1])
				y--;
			else {
				char scoreA = a.get(x - 1).Repetition;
				int scoreB = b.get(y - 1).Repetition; // testdata, must be int,
														// because char is
														// unsigned
				int index = 0;
				int xx = x - 1;
				while ((scoreB > 0) && (xx < a.size())) {
					if (a.get(xx).Observation != b.get(y - 1).Observation) {
						// TODO: check more about score here
						// result.sequenceinFile.getLast().Repetition+=scoreB;
						break;
					}
					SequenceElement se = new SequenceElement(a.get(xx));

					scoreB -= se.Repetition;
					if (scoreB < 0)
						se.Repetition += scoreB;
					result.sequenceinFile.add(index, se);

					xx += 1;
					++index;
				}
				x--;
				y--;

			}
		}
		// TODO: check if needed
		if (a.BusRouteID != 0)
			result.BusRouteID = a.BusRouteID;
		else if (b.BusRouteID != 0)
			result.BusRouteID = b.BusRouteID;
		return result;
	}

	// UTILITIES
	private void writeSequenceToBinary(LinkedList<Sequence> seqs) {
		try {
			DataOutputStream out = new DataOutputStream(new FileOutputStream(
					CONSTANTS.REFINED_SEQUENCE_BINARY_FILEPATH));
			this.writeSequenceToBinary(out, seqs);
			out.close();
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

	private LinkedList<Sequence> readSequenceFromBinary() {
		try {
			DataInputStream in = new DataInputStream(new FileInputStream(
					CONSTANTS.REFINED_SEQUENCE_BINARY_FILEPATH));
			return readSequenceFromBinary(in);
		} catch (Exception e1) {
			e1.printStackTrace();
		}
		return null;

	}

	private void writeSequenceToBinary(DataOutputStream out,
			LinkedList<Sequence> seqs) {
		try {
			for (int i = 0; i < seqs.size(); i++) {
				Sequence seq = seqs.get(i);
				out.writeInt(seq.BusRouteID);
				out.writeInt(seq.size());
				for (SequenceElement seqel : seq.sequenceinFile) {
					seqel.writeBinary(out);
				}
			}
			out.close();
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

	private LinkedList<Sequence> readSequenceFromBinary(DataInputStream in) {
		LinkedList<Sequence> result = new LinkedList<Sequence>();
		try {
			SequenceElement seqel;
			int size;
			while (true) {
				try {
					// read a sequence
					Sequence seq = new Sequence();
					seq.BusRouteID = in.readInt();
					size = in.readInt();
					for (int i = 0; i < size; i++) {
						seqel = new SequenceElement();
						seqel.readBinary(in);
						if (seqel.Repetition == 0)
							seqel.Repetition = 1;
						seq.add(seqel);
					}
					result.add(seq);

				} catch (Exception e) {
					break;
				}
			}
		} catch (Exception e1) {
			e1.printStackTrace();
		}
		return result;
	}

	// POSSIBLE BUSROUTE FROM SEQUENCE MATCHING
	// 99.8
	public short[] possibleBusRoute(Sequence sequence) {
		LinkedList<Short> result = new LinkedList<Short>();

		sequence = sequence.refineSequence();
		Sequence[] matchedSeqs = new Sequence[CONSTANTS.ALLBUSROUTE.length];
		int[] score = new int[CONSTANTS.ALLBUSROUTE.length];

		int index = 0;
		for (int i = 0; i < CONSTANTS.ALLBUSROUTE.length; i++) {
			index = findBusrouteIndex(CONSTANTS.ALLBUSROUTE[i]);
			if (index != -1) {
				if (refined_seqs.get(index).BusRouteID == sequence.BusRouteID)
					System.out.println("HERE");
				matchedSeqs[i] = lcs(refined_seqs.get(index), sequence);

				score[i] = matchedSeqs[i].score();

			} else
				score[i] = 0;
		}
		// TODO: We can vary minscore (minscore=*.8minscore to maxout accuracy)
		double minScore = Utils.max(score);
		// minScore = minScore*0.8;

		// TODO: debug tools
		int[] matchedBusroute = Utils.findAllMaxInArray(score);
		for (int i = 0; i < matchedBusroute.length; i++) {
			if (matchedSeqs[matchedBusroute[i]] != null)
				result.add((short) matchedSeqs[matchedBusroute[i]].BusRouteID);
		}

		short[] result2 = new short[result.size()];
		result2[0] = result.get(0);

		return result2;

	}

	// POSSIBLE BUSROUTE FROM OBSERVATION
	public LinkedList<Short> possibleBusRoute(
			LinkedList<Character> observationList) {
		LinkedList<Short> result = new LinkedList<Short>();

		boolean isIn = true;
		for (Sequence seq : refined_seqs) {
			isIn = true;
			for (Character observation : observationList) {
				if (!observationExistsInRoute(seq, observation)) {
					isIn = false;
					break;
				}
			}
			if (isIn)
				result.add((short) seq.BusRouteID);
		}
		return result;
	}

	public short[] possibleBusRoute(Character observation) {
		// overload posibleBusRoute
		LinkedList<Character> observationList = new LinkedList<Character>();
		observationList.add(observation);
		LinkedList<Short> temp = possibleBusRoute(observationList);
		// TODO: check here
		if (temp.size() == 0)
			return new short[] { 0 };
		short[] result = new short[temp.size()];
		for (int i = 0; i < temp.size(); i++) {
			result[i] = temp.get(i);
		}
		return result;
	}

	public boolean observationExistsInRoute(Sequence seq, char observation) {
		for (int i = 0; i < seq.size(); i++) {
			if (seq.get(i).Observation == observation)
				return true;
		}
		return false;
	}

}
